// Package search implements a search for the best move in a chess position.
package search

import (
	b "code.google.com/p/gochess/board"
	"code.google.com/p/gochess/config"
	"code.google.com/p/gochess/movement"
	"code.google.com/p/gochess/notation/cn"
	"code.google.com/p/gochess/notation/lan"
	pos "code.google.com/p/gochess/position"
	"code.google.com/p/gochess/search/log"
	stats "code.google.com/p/gochess/statistics"
	"fmt"
	"strings"
	"time"
)

// Flags for setting search parameters
// todo: remove PrintPV
const (
	PrintPV    uint32 = 1 << iota // print principal variation after each iteration
	NoTT                          // disable transposition table
	NoCutOffs                     // don't apply beta cut offs
	NoQSearch                     // disable quiescence search
	NoLMR                         // disable late move reduction
	NoKiller                      // disable killer move heuristic
	NoNullMove                    // disable null moves
	NoPVS                         // disable pvs
	insidePV                      // search is inside pv
	perftMode  = NoTT |
		NoCutOffs | NoQSearch | NoLMR | NoPVS // mode for perft tests
)

const (
	// checkmateScore represents the checkmate score.
	// A player is checkmate if the difference of the material score
	// of both sides is higher than checkmateScore
	checkmateScore int32 = 9*queenValue + 2*rookValue + 2*bishopValue + 2*knightValue + 1

	checkmateReturnScore int32 = checkmateScore + 1000
)

var (
	logger  log.FileLogger
	logfile string
)

type node struct {
	moves            movement.Movelist
	killer1, killer2 pos.Move
}

func (this *node) saveKiller(move pos.Move) {
	if this.killer1 != move {
		this.killer2 = this.killer1
		this.killer1 = move
	}
}

func (n *node) String() string {
	return fmt.Sprintf("moves: %v; killer 1, 2: %v, %v", &n.moves, n.killer1, n.killer2)
}

type nodePath struct {
	path    []node
	current int
}

func (np *nodePath) reset() {
	np.current = 0
	np.path = np.path[:0]
}

func (np *nodePath) clearKillers() {
	for i := 0; i < len(np.path); i++ {
		np.path[i].killer1, np.path[i].killer2 = pos.NoMove, pos.NoMove
	}
}

func (np *nodePath) appendOne() {
	np.path = append(np.path, node{})
}

func (np *nodePath) take() *node {
	np.current++
	return &np.path[np.current-1]
}

func (np *nodePath) put() {
	np.current--
}

func (np *nodePath) String() string {

	s := []string{fmt.Sprintf("current: %d", np.current)}
	for i := range np.path {
		s = append(s, fmt.Sprintf("%d: %v", i, &np.path[i]))
	}
	return strings.Join(s, "\n")
}

type pvTriangle struct {
	values        [][]pos.Move
	current, lock int
}

func (pvt *pvTriangle) clear() {
	pvt.values, pvt.current, pvt.lock = [][]pos.Move{}, 0, 0
}

func (pvt *pvTriangle) grow() {
	pvt.values = append(pvt.values, make([]pos.Move, len(pvt.values)+2))
}

func (pvt *pvTriangle) descend() {
	pvt.current--
}

func (pvt *pvTriangle) ascend() {
	pvt.current++
}

func (pvt *pvTriangle) save(move pos.Move) {
	pvt.values[pvt.current-1][0] = move
	if pvt.current > 1 {
		copy(pvt.values[pvt.current-1][1:], pvt.values[pvt.current-2])
	}
}

func (pvt *pvTriangle) lockPV() {
	pvt.lock = pvt.current - 1
}

func (pvt *pvTriangle) pvNext() pos.Move {
	return pvt.values[pvt.lock][len(pvt.values)-pvt.current]
}

func (pvt *pvTriangle) pv() []pos.Move {
	return pvt.values[pvt.lock][:len(pvt.values[pvt.lock])-1]
}

func (pvt *pvTriangle) String() string {

	s := []string{fmt.Sprintf("current: %d, lock: %d", pvt.current, pvt.lock)}
	for i := len(pvt.values) - 1; i >= 0; i-- {
		s = append(s, fmt.Sprintf("%d: %v", i, pvt.values[i]))
	}
	return strings.Join(s, "\n")
}

func timeIsUp() bool {
	return time.Now().UnixNano() >= int64(timeToStop)
}

var (
	// for time bound termination
	nodesCheckpoint,
	timeToStop,
	nodesChecked int64

	path nodePath
	pvt  pvTriangle
)

func SetLogFile(file string) {
	logfile = file
}

// Stop stops a search.
func Stop() {
	timeToStop = 0 // force time is up
}

// Run searches for the best move in the given position.
// It returns this move and a score for the position, which results in making
// the returned move.
func Run(p *pos.Position, lastMove pos.Move, duration time.Duration, depth int32, flags uint32) (pos.Move, int32) {
	out := make(chan string)
	var move pos.Move
	var score int32
	go func() {
		defer close(out)
		move, score = search(p, lastMove, duration, depth, flags, out)
	}()
	for _ = range out {
		// wait for search to finnish
	}
	return move, score
}

var perftCount int64

// Perft runs a search and returns the perft count
// (number of all leafs in the search tree).
func Perft(p *pos.Position, lastMove pos.Move, depth int32) int64 {
	if depth == 0 {
		return 1
	}
	nodesCheckpoint, nodesChecked = 1<<63-1, 0
	perftCount = 0
	Run(p, lastMove, 0, depth, perftMode)
	return perftCount
}

// RunUCISearch searches for the best move in the given position.
// It returns this move and a score for the position, which results in making
// the returned move.
// This Function will read UCI commands from in and write UCI informations
// to out. The out channel will be closed when the search is done.
func RunUCISearch(p *pos.Position, lastMove pos.Move, duration time.Duration, depth int32, flags uint32, out chan<- string) {

	go func() {
		defer close(out)
		search(p, lastMove, duration, depth, flags, out)
	}()
}

func search(p *pos.Position, lastMove pos.Move, duration time.Duration, depth int32, flags uint32, out chan<- string) (pos.Move, int32) {

	if config.Log {
		if len(logfile) == 0 {
			panic("logging is enabled, but logfile is not set")
		}
		logger = *log.NewFileLogger(logfile)
		logger.Start(p)
		defer logger.Stop()
	}
	if depth == 0 {
		depth = 31<<1 - 1
	}
	timeToStop = 1<<63 - 1
	if duration != 0 {
		timeToStop = time.Now().UnixNano() + int64(duration)
	}
	nodesCheckpoint, nodesChecked = 100000, 0

	path.reset()
	path.appendOne()
	node := path.take()
	rootMoves := &node.moves
	pvt.clear()
	var attacks int32
	var from b.Square
	if lastMove == pos.NoMove {
		attacks, from = movement.DetectCheck(p)
	} else {
		attacks, from = movement.DetectCheckByLastMove(p, lastMove)
	}
	if attacks == 0 {
		movement.GenerateSortedLegalMoves(p, rootMoves)
		if rootMoves.Len() == 0 {
			return pos.NoMove, 0
		}
	} else {
		movement.GenerateCheckEvasions(p, attacks, from, rootMoves)
		if rootMoves.Len() == 0 {
			return pos.NoMove, -checkmateReturnScore
		}
	}

	var prevMove, pvMove pos.Move
	var prevScore, alpha, beta int32
	var pv []string
	sp := newPosition(p)
	// iterative deepening
	for i := int32(1); i <= depth; i++ {
		perftCount = 0
		out <- fmt.Sprintf("info depth %d", i)
		_ = config.Log && logger.EnterIteration(i)
		path.clearKillers()
		if i != 1 {
			path.appendOne()
		}
		pvt.grow()
		pvt.ascend()
		rootMoves.Rewind()
		rootMoves.Sort()
		// "+ depth" as bonus for early mate
		alpha, beta = -(checkmateReturnScore + depth), checkmateReturnScore+depth
		var cur int
		flags |= insidePV
		if !config.PVS {
			flags &^= insidePV
		}
		var score int32
		for move := rootMoves.Next(); move != pos.NoMove; move = rootMoves.Next() {
			if i > 5 {
				cur++
				out <- fmt.Sprintf("info currmove %s currmovenumber %d", cn.Sprint(move, p.SideToMove()), cur)
			}
			if config.Log {
				logger.Printf("inside pvs: %t", flags&insidePV != 0)
				logger.Printf("%s plays %v", p.SideToMove(), sprintMove(p, move))
				logger.EnterSearch(&sp.Position, move, true)
			}
			uMove := pos.MakeMove(sp, move)
			if i == 1 || flags&insidePV == 0 {
				score = -negamax(sp, move, -beta, -alpha, i-1, flags)
			} else {
				score = -negamax(sp, move, -alpha-1, -alpha, i-1, flags)
				if score > alpha {
					score = -negamax(sp, move, -beta, -alpha, i-1, flags)
				}
			}
			_ = config.Log && logger.LeaveSearch(true)
			pos.UnmakeMove(sp, uMove)
			if score > alpha {
				// todo: pv info to uci out
				_ = config.Log && logger.Printf("move %s raises alpha from %d to %d", sprintMove(p, move), alpha, score)
				alpha, pvMove = score, move
				pvt.save(pvMove)
			}
			rootMoves.SetWeight(score)
			if timeIsUp() {
				break
			}
			flags &^= insidePV
		}
		pvt.lockPV()
		if timeIsUp() {
			_ = config.Log && logger.Print("time over")
			// return result of last iteration
			alpha, pvMove = prevScore, prevMove
			break
		}
		if flags&PrintPV != 0 {
			fmt.Println(showPV(sp, p.SideToMove(), i))
		}
		if (alpha < -checkmateScore || alpha > checkmateScore) && flags != perftMode {
			_ = config.Log && logger.Print("check mate")
			break
		}
		// make sure the pv move is played first
		//rootMoves.Rewind()
		//for move := rootMoves.Next(); move != pvMove; move = rootMoves.Next() {
		//}
		//rootMoves.SetWeight(movement.MaxMoveSortValue)
		prevMove = pvMove
		prevScore = alpha
		if config.Log {
			logger.Printf("all moves played, alpha=%d, best move=%s", alpha, sprintMove(p, pvMove))
			logger.LeaveIteration(i)
		}
		pv = pv[:0]
		stm := p.SideToMove()
		for _, move := range extractPV(sp, i, pvMove) {
			// for _, move := range pvt.pv() {
			pv = append(pv, cn.Sprint(move, stm))
			stm = pos.Opponent(stm)
		}
		nodes := stats.SearchNodes + stats.NodesQuiescence
		out <- fmt.Sprintf("info depth %d nodes %d time %d nps %d score cp %d hashfull %d pv %s",
			i, nodes, stats.Duration()/time.Millisecond, stats.CalcNPS(nodes), alpha,
			Transpositions.Filled(), strings.Join(pv, ` `))
		_ = config.Log && logger.Printf("pv: %v", pvt.pv())
	}
	path.put()
	_ = config.Log && logger.Printf("<- move=%s, score=%d", sprintMove(p, pvMove), alpha)
	out <- fmt.Sprintf("bestmove %s", cn.Sprint(pvMove, p.SideToMove()))
	return pvMove, alpha
}

// move generation stages. Order does matter, do not change.
const (
	stageHashmove = iota
	stageCaptures
	stageKillers
	stageQuietMoves
	stageCheckEvasions
	stageQCheckEvasions
	stageQCaptures

	// from that stage on consider lmr
	// todo: not used
	stageLMR = stageQuietMoves

	// reduce dearch depth by this when using lmr
	lmrDepth = 1
)

var stages = []string{
	"hash move", "captures", "killers", "pieve moves", "pawn moves and castlings",
}

func negamax(sp *position, lastPly pos.Move, alpha, beta, depth int32, flags uint32) int32 {

	_ = config.Log && logger.Printf("-> depth=%d, stm=%s, last move=%s, alpha=%d, beta=%d, pv=%t",
		depth, sp.SideToMove(), lastPly, alpha, beta, flags&insidePV != 0)
	nodesChecked++
	if nodesChecked >= nodesCheckpoint {
		if timeIsUp() {
			if config.Log {
				logger.Print("time over")
				logger.Printf("<- score=%d", 0)
			}
			// this return value is not used anyway
			return 0
		}
		nodesChecked = 0
	}
	pvt.descend()
	var hashMove pos.Move
	// pv is broken
	//if flags&insidePV != 0 && depth > 0 {
	//	// pv
	//	hashMove = pvt.pvNext()
	//	if hashMove == pos.NoMove {
	//		_ = config.Log && logger.Printf("no pv move available, trying hash move")
	//	}
	//}
	// check for transposition table information
	if flags&NoTT == 0 && hashMove == pos.NoMove {
		if posInfo := Transpositions.get(sp.Hash()); posInfo != 0 {
			stats.TTHits++
			hashMove = posInfo.Move()
			_ = config.Log && logger.Printf("tthit; tt->hashMove=%s", sprintMove(&sp.Position, hashMove))
			// todo: is this correct? ALL_NODEs dont have a move saved in the table!
			if ok, score := probePosition(posInfo, alpha, beta, depth); ok {
				stats.GoodTTHits++
				// don't cut at pv, as we want the entire pv
				if flags&insidePV == 0 {
					if config.Log {
						logger.Print("tt cutoff")
						logger.Printf("<- score=%d", score)
					}
					pvt.ascend()
					return score
				}
				alpha = score
			}
		}
	}
	if depth == 0 {
		var score int32
		stats.LeafNodes++
		perftCount++
		// todo: extend by one ply if stm is in check
		if flags&NoQSearch == 0 {
			_ = config.Log && logger.EnterQuiescence(&sp.Position, pos.NoMove, true)
			score = quiescence(sp, lastPly, alpha, beta, 0)
			_ = config.Log && logger.LeaveQuiescence(true)
		} else {
			score = evaluate(sp)
		}
		// todo: enable save then quiescence is settled. some test did
		// show this save is a good idea
		// Transpositions.save(sp.Hash(), pos.NoMove, score, depth, pVNode)
		_ = config.Log && logger.Printf("<- score=%d", score)
		pvt.ascend()
		return score
	}

	stats.InnerNodes++
	nodeType := allNode
	var bestMove pos.Move
	var movesFound, moveMade bool
	node := path.take()

	// first try hash move
	// BUG: should i check validity of hash move? YES
	// todo: when inside pv, dont play hash move, but pv move
	if hashMove != pos.NoMove {
		_ = config.Log && logger.Print("enter stage: ", stages[stageHashmove])
		stats.Nodes[stageHashmove]++
		stats.SearchNodes++
		movesFound, moveMade = true, true
		_ = config.Log && logger.EnterSearch(&sp.Position, hashMove, false)
		uMove := pos.MakeMove(sp, hashMove)
		score := -negamax(sp, hashMove, -beta, -alpha, depth-1, flags)
		pos.UnmakeMove(sp, uMove)
		_ = config.Log && logger.LeaveSearch(false)
		// todo: if there was a mate in 1 turn, return this move
		if score >= beta && flags&NoCutOffs == 0 {
			_ = config.Log && logger.Printf("move=%s, score=%d, depth=%d, node=%s ->tt", sprintMove(&sp.Position, hashMove), beta, depth, cutNode)
			Transpositions.save(sp.Hash(), hashMove, beta, depth, cutNode)
			if config.Log {
				logger.Print("beta cutoff from hash move")
				logger.Printf("<- score=%d", beta)
			}
			stats.CutOffs[stageHashmove]++
			path.put()
			pvt.ascend()
			return beta
		}
		if score > alpha {
			_ = config.Log && logger.Printf("hash move %s raises alpha from %d to %d", sprintMove(&sp.Position, hashMove), alpha, score)
			nodeType, alpha, bestMove = pVNode, score, hashMove
			stats.AlphaRaises[stageHashmove]++
			pvt.save(hashMove)
		}
	}

	p := &sp.Position
	moves := &node.moves

	// generating moves depending on the "in check" status
	if attacks, from := movement.DetectCheckByLastMove(p, lastPly); attacks > 0 {
		_ = config.Log && logger.Print("in check")
		stats.SearchInCheck++
		moves.Clear()
		movement.GenerateCheckEvasions(p, attacks, from, moves)
		if moves.Len() == 0 {
			// check mate
			// BUG: problems with mate scores
			Transpositions.save(sp.Hash(), pos.NoMove, -checkmateReturnScore-depth, depth, pVNode)
			if config.Log {
				logger.Print("checkmate")
				logger.Printf("<- score=%d", -checkmateReturnScore-depth)
			}
			path.put()
			pvt.ascend()
			return -checkmateReturnScore - depth
		}
		// bug: side to move could mate the opponent, this is wrong
		//if position.IsDrawBy50MoveRule() {
		//	//logger.Print("draw by 50 move rule")
		//	//logger.Printf("<- move=%s, score=%d", pos.NoMove, 0)
		//	return pos.NoMove, 0
		//}
		moves.Sort()
		// check evasions
		// todo: save killers here too, if move is quiet
		var score int32
		for move := moves.Next(); move != pos.NoMove; move = moves.Next() {
			// dont evaluate hash move twice
			if move != hashMove {
				stats.SearchNodes++
				stats.Nodes[stageCheckEvasions]++
				_ = config.Log && logger.EnterSearch(&sp.Position, move, false)
				uMove := pos.MakeMove(sp, move)
				if hashMove == pos.NoMove && flags&insidePV != 0 || !config.PVS {
					score = -negamax(sp, move, -beta, -alpha, depth-1, flags)
				} else {
					score = -negamax(sp, move, -alpha-1, -alpha, depth-1, flags)
					if score > alpha {
						score = -negamax(sp, move, -beta, -alpha, depth-1, flags)
					}
					flags &^= insidePV
				}
				pos.UnmakeMove(sp, uMove)
				_ = config.Log && logger.LeaveSearch(false)
				// todo: if there was a mate in 1 turn, return this move
				if score >= beta && flags&NoCutOffs == 0 {
					stats.CutOffs[stageCheckEvasions]++
					Transpositions.save(sp.Hash(), move, beta, depth, cutNode)
					if config.Log {
						logger.Printf("score %d >= beta %d: beta cutoff", score, beta)
						logger.Printf("move=%s, score=%d, depth=%d, node=%s ->tt", sprintMove(&sp.Position, move), beta, depth, cutNode)
						logger.Printf("<- score=%d", beta)
					}
					path.put()
					pvt.ascend()
					return beta
				}
				if score > alpha {
					_ = config.Log && logger.Printf("move=%s raises alpha from %d to %d", sprintMove(&sp.Position, move), alpha, score)
					stats.AlphaRaises[stageCheckEvasions]++
					nodeType, alpha, bestMove = pVNode, score, move
					pvt.save(move)

				}
				flags &^= insidePV
			}
		}
	} else {
		// side to move is not in check
		//logger.Print("not in check")
		//if position.IsDrawBy50MoveRule() {
		//	// position is draw
		//	//logger.Print("draw by 50 move rule")
		//	//logger.Printf("<- move=%s, score=%d", pos.NoMove, 0)
		//	return pos.NoMove, 0
		//}
		var lmrHere int32
		if config.LMR && depth >= 3 && flags&NoLMR == 0 {
			lmrHere = lmrDepth
		}
		var killer1, killer2 pos.Move
		var score int32
		// staged move generation
		for stage := stageCaptures; stage <= stageQuietMoves; stage++ {
			// disable lmr for the first stages
			var lmr int32
			_ = config.Log && logger.Print("enter stage: ", stages[stage])
			switch stage {
			case stageCaptures:
				moves.Clear()
				// todo: we should put underpromotions to non captures
				movement.GeneratePieceCaptures(p, moves)
				movement.GeneratePawnCapturesAndPromotions(p, moves)
				moves.Sort()
			case stageKillers:
				if flags&NoKiller == 0 {
					moves.Clear()
					loadLegalKillers(p, node, moves)
					killer1, killer2 = moves.Next(), moves.Next()
					moves.Rewind()
				}
			case stageQuietMoves: // quiet piece moves
				lmr = lmrHere //use lmr from now on, if appropriate
				moves.Clear()
				movement.GenerateCastlings(p, moves)
				movement.GeneratePieceMoves(p, moves)
				movement.GeneratePawnMoves(p, moves)
				moves.Sort()
			}
			stats.Nodes[stage]++
			for move := moves.Next(); move != pos.NoMove; move = moves.Next() {
				movesFound = true
				// don't try hash move twice and ignore killers after killer stage
				if move == hashMove || stage > stageKillers && (move == killer1 || move == killer2) {
					continue
				} else if !movement.IsLegalMoveWhileNotInCheck(p, move) {
					stats.RejectedMoves++
					continue
				}
				lmr1 := lmr
				moveMade = true
			ReSearch:
				stats.SearchNodes++
				_ = config.Log && logger.EnterSearch(&sp.Position, move, false)
				uMove := pos.MakeMove(sp, move)
				if hashMove == pos.NoMove && flags&insidePV == 0 || !config.PVS {
					score = -negamax(sp, move, -beta, -alpha, depth-1-lmr1, flags)
				} else {
					score = -negamax(sp, move, -alpha-1, -alpha, depth-1-lmr1, flags)
					if score > alpha {
						score = -negamax(sp, move, -beta, -alpha, depth-1-lmr1, flags)
					}
					flags &^= insidePV
				}
				pos.UnmakeMove(sp, uMove)
				_ = config.Log && logger.LeaveSearch(false)
				// todo: if there was a mate in 1 turn, return this move
				if score >= beta && flags&NoCutOffs == 0 {
					if lmr1 != 0 {
						lmr1 = 0
						_ = config.Log && logger.Printf("lmr: score %d >= beta %d, research move with full depth",
							score, beta)
						goto ReSearch
					}
					_ = config.Log && logger.Printf("score %d >= beta %d: beta cutoff", score, beta)
					if stage > stageKillers {
						stats.KillerSaves++
						_ = config.Log && logger.Printf("saving killer %v", move)
						node.saveKiller(move)
					}
					stats.CutOffs[stage]++
					Transpositions.save(sp.Hash(), move, beta, depth, cutNode)
					if config.Log {
						logger.Printf("tt <- move=%s, score=%d, depth=%d, node=%s", sprintMove(&sp.Position, move), beta, depth, cutNode)
						logger.Printf("score=%d", beta)
					}
					path.put()
					pvt.ascend()
					return beta
				}
				if score > alpha {
					if lmr1 != 0 {
						lmr1 = 0
						_ = config.Log && logger.Printf("lmr: score %d > alpha %d, research move with full depth",
							score, alpha)
						goto ReSearch
					}
					_ = config.Log && logger.Printf("move=%s raises alpha from %d to %d", sprintMove(&sp.Position, move), alpha, score)
					stats.AlphaRaises[stage]++
					nodeType, alpha, bestMove = pVNode, score, move
					pvt.save(move)
				}
				flags &^= insidePV
			}
		}
		// assert
		if config.Debug && !movesFound {
			panic(fmt.Sprintf("No moves at the beginning of search.negamax(), not possible. lasty ply: %v, search position: %v",
				lastPly, sp))
		}
		if !moveMade {
			// todo: how to store stalemate in tt?
			if config.Log {
				logger.Print("stalemate")
				logger.Printf("<- score=%d", 0)
			}
			path.put()
			pvt.ascend()
			return 0
		}
	} // else - if InCheck(sp, lastPly) {

	//		if nodeType == pVNode {
	Transpositions.save(sp.Hash(), bestMove, alpha, depth, nodeType)
	_ = config.Log && logger.Printf("tt <- move=%s, score=%d, depth=%d, node=%s",
		sprintMove(&sp.Position, bestMove), alpha, depth, nodeType)
	//		}
	if config.Log {
		logger.Printf("node=%s", nodeType)
		logger.Printf("<- score=%d", alpha)
	}
	path.put()
	pvt.ascend()
	return alpha
}

func loadLegalKillers(p *pos.Position, node *node, killers *movement.Movelist) {
	if node.killer1 != pos.NoMove {
		stats.Killer1Available++
		if movement.IsQuietPseudoLegalMove(p, node.killer1) {
			stats.Killer1PseudoLegal++
			killers.Append(node.killer1, 0)
		}
		if node.killer2 != pos.NoMove {
			stats.Killer2Available++
			if movement.IsQuietPseudoLegalMove(p, node.killer2) {
				stats.Killer2PseudoLegal++
				killers.Append(node.killer2, 0)
			}
		}
	}
}

var quiescenceCache [32]movement.Movelist

// todo: mate, stalemate detection
// todo: UnderAttack is called very often, find out why
func quiescence(sp *position, lastPly pos.Move, alpha, beta, depth int32) int32 {

	_ = config.Log && logger.Printf("-> depth=%d, stm=%s, last move=%s, alpha=%d, beta=%d",
		depth, sp.SideToMove(), lastPly, alpha, beta)
	nodesChecked++
	if nodesChecked >= nodesCheckpoint {
		if timeIsUp() {
			if config.Log {
				logger.Print("time over")
				logger.Printf("<- score=%d", 0)
			}
			return alpha
		}
		nodesChecked = 0
	}
	// bug: don't do this if we are in check
	score := evaluate(sp)
	_ = config.Log && logger.Print("eval: ", score)
	if score >= beta {
		if config.Log {
			logger.Printf("eval score %d >= beta %d: beta cutoff", score, beta)
			logger.Printf("<- score=%d", beta)
		}
		return beta
	}
	if score > alpha {
		_ = config.Log && logger.Printf("last ply %s raises alpha from  %d to eval score %d",
			lastPly, alpha, score)
		alpha = score
	}
	p := &sp.Position
	moves := &(quiescenceCache[depth])

	if attacks, from := movement.DetectCheckByLastMove(p, lastPly); attacks > 0 {
		stats.QuiesceInCheck++
		_ = config.Log && logger.Print("in check")
		score = -(checkmateReturnScore + depth)
		moves.Clear()
		movement.GenerateCheckEvasions(p, attacks, from, moves)
		if moves.Len() == 0 {
			if config.Log {
				logger.Print("checkmate")
				logger.Printf("<- score=%d", -checkmateReturnScore+depth)
			}
			return -checkmateReturnScore + depth
		}
		moves.Sort()
		// check evasions
		for move := moves.Next(); move != pos.NoMove; move = moves.Next() {
			stats.Nodes[stageQCheckEvasions]++
			stats.NodesQuiescence++
			_ = config.Log && logger.EnterQuiescence(p, move, false)
			uMove := pos.MakeMove(sp, move)
			score = -quiescence(sp, move, -beta, -alpha, depth+1)
			pos.UnmakeMove(sp, uMove)
			_ = config.Log && logger.LeaveQuiescence(false)
			if score >= beta {
				// todo: stageCheckEvasionsstats.BetaCutOffs++
				if config.Log {
					logger.Printf("score %d >= beta %d: beta cutoff", score, beta)
					logger.Printf("<- score=%d", beta)
				}
				stats.CutOffs[stageQCheckEvasions]++
				return beta
			}
			if score > alpha {
				_ = config.Log && logger.Printf("move %s raises alpha from %d to %d",
					sprintMove(&sp.Position, move), alpha, score)
				stats.AlphaRaises[stageQCheckEvasions]++
				alpha = score
			}
		}
	} else {
		moves.Clear()
		movement.GeneratePawnCapturesAndQueenPromotions(p, moves)
		movement.GeneratePieceCaptures(p, moves)
		if moves.Len() == 0 {
			_ = config.Log && logger.Print("no captures")
			_ = config.Log && logger.Printf("<- score=%d", alpha)
			return alpha
		}
		moves.Sort()
		for move := moves.Next(); move != pos.NoMove; move = moves.Next() {
			if !movement.IsLegalMoveWhileNotInCheck(p, move) {
				stats.RejectedMoves++
				continue
			}
			stats.Nodes[stageQCaptures]++
			stats.NodesQuiescence++
			_ = config.Log && logger.EnterQuiescence(&sp.Position, move, false)
			uMove := pos.MakeMove(sp, move)
			score = -quiescence(sp, move, -beta, -alpha, depth+1)
			pos.UnmakeMove(sp, uMove)
			_ = config.Log && logger.LeaveQuiescence(false)
			if score >= beta {
				if config.Log {
					logger.Printf("score %d >= beta %d: beta cutoff", score, beta)
					logger.Printf("<- score=%d", beta)
				}
				stats.CutOffs[stageQCaptures]++
				return beta
			}
			if score > alpha {
				_ = config.Log && logger.Printf("move %s raises alpha from %d to %d",
					sprintMove(&sp.Position, move), alpha, score)
				stats.AlphaRaises[stageQCaptures]++
				alpha = score
			}
		}
	}
	_ = config.Log && logger.Print("<- score ", alpha)
	return alpha
}

// RootMoves returns the moves of the root using a depth=1 Perft search.
// It is used in conjunction with Perft to print a list of all moves
// in a position and the computed perft count.
func RootMoves(p *pos.Position, lastMove pos.Move) []pos.Move {
	var root []pos.Move
	Perft(p, lastMove, 1)
	node := path.take()
	moves := node.moves
	moves.Rewind()
	for move := moves.Next(); move != pos.NoMove; move = moves.Next() {
		root = append(root, move)
	}
	moves.Clear()
	path.put()
	// todo: do we have to clear the killers too?
	return root
}

var pvMoves []pos.MoveUnmaking

func showPV(p *position, sideToMove pos.Color, depth int32) string {

	output := fmt.Sprintf("%d: ", depth)
	pvMoves = pvMoves[:0]
	var score int32
	for i := int32(0); i <= depth; i++ {
		// fix the statistics
		stats.HashGetRequests--
		posInfo := Transpositions.get(p.Hash())
		if posInfo == 0 || posInfo.NodeType() != pVNode ||
			posInfo.Move() == pos.NoMove {
			break
		}
		output += fmt.Sprintf("%s ", sprintMove(&p.Position, posInfo.Move()))
		pvMoves = append(pvMoves, pos.MakeMove(p, posInfo.Move()))
		score = posInfo.Score()
	}
	if p.Position.SideToMove() == sideToMove {
		// equal, as the side is changed after the last move
		score = -score // adjust score for opponent
	}
	for i := len(pvMoves) - 1; i >= 0; i-- {
		pos.UnmakeMove(p, pvMoves[i])
	}
	return output + fmt.Sprintf("- score: %v", score)

}

func extractPV(sp *position, depth int32, firstMove pos.Move) []pos.Move {

	pvMoves = pvMoves[:0]
	pv := []pos.Move{firstMove}
	uMove := pos.MakeMove(sp, firstMove)
	for i := int32(1); i <= depth; i++ {
		// fix the statistics
		stats.HashGetRequests--
		posInfo := Transpositions.get(sp.Hash())
		if posInfo == 0 || posInfo.NodeType() != pVNode || posInfo.Move() == pos.NoMove {
			break
		}
		pv = append(pv, posInfo.Move())
		pvMoves = append(pvMoves, pos.MakeMove(sp, posInfo.Move()))
	}
	for i := len(pvMoves) - 1; i >= 0; i-- {
		pos.UnmakeMove(sp, pvMoves[i])
	}
	pos.UnmakeMove(sp, uMove)
	return pv
}

func sprintMove(p *pos.Position, move pos.Move) string {
	if move == pos.NoMove {
		return "NoMove"
	}
	return lan.SprintMove(p, move)
}
